package wh.长度最小的子数组;

import com.sun.xml.internal.ws.addressing.WsaTubeHelperImpl;

import java.util.*;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/4 10:12
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        int i = minSubArrayLen(11, arr);
        System.out.println(i);
    }


    //队列相加 滑动窗口的思想，确定左右两个边界
    public static int minSubArrayLen(int target, int[] nums) {
        int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            sum += nums[hi++];
            while (sum >= target) {
                min = Math.min(min, hi - lo);
                sum -= nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }


    //队列相减
    public static int minSubArrayLen2(int s, int[] nums) {
        int lo = 0, hi = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            s -= nums[hi++];
            while (s <= 0) {
                min = Math.min(min, hi - lo);
                s += nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    //二分查找
    public int minSubArrayLen3(int s, int[] nums) {
        int length = nums.length;
        int min = Integer.MAX_VALUE;
        int[] sums = new int[length + 1];
        for (int i = 1; i <= length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 0; i <= length; i++) {
            int target = s + sums[i];
            int index = Arrays.binarySearch(sums, target);
            if (index < 0)
                index = ~index;
            if (index <= length) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }


    //直接使用窗口
    public int minSubArrayLen4(int s, int[] nums) {
        int lo = 1, hi = nums.length, min = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (windowExist(mid, nums, s)) {
                hi = mid - 1;//找到就缩小窗口的大小
                min = mid;//如果找到就记录下来
            } else
                lo = mid + 1;//没找到就扩大窗口的大小
        }
        return min;
    }

    //size窗口的大小
    private boolean windowExist(int size, int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i >= size)
                sum -= nums[i - size];
            sum += nums[i];
            if (sum >= s)
                return true;
        }
        return false;
    }


}
